package treesNgraphs;

import java.util.*;

/**
 * Created by Tzachi on 15/10/2014.
 *
 * Find path to all vertexes from single source
 * The full solution will need to build a dijkstra graph on top of the adj list input graph,
 * since the common graph is only adjacent list without properties like previous and distance to source
 *
 */

public class Dijkstra {
    /**
     * The Dikjstra algorithm
     */
    public static void computePaths(DijkstraVertex source, List<DijkstraVertex> nodes) {
        PriorityQueue<DijkstraVertex> dijkstraVertexQueue = new PriorityQueue<>(nodes);
        source.minDistanceToSource = 0;
        dijkstraVertexQueue.add(source);

        while (!dijkstraVertexQueue.isEmpty()) {
            DijkstraVertex u = dijkstraVertexQueue.poll();

            // Visit each edge exiting u
            for (DijkstraEdge e : u.adjacencies) {
                DijkstraVertex v = e.target;
                double weight = e.weight;
                double distanceThroughU = u.minDistanceToSource + weight;
                if (distanceThroughU < v.minDistanceToSource) {
                    v.minDistanceToSource = distanceThroughU;
                    v.previous = u;
                }
            }
        }
    }

    public static List<DijkstraVertex> getShortestPathTo(DijkstraVertex target)
    {
        List<DijkstraVertex> path = new ArrayList<>();
        for (DijkstraVertex vertex = target; vertex != null; vertex = vertex.previous)
            path.add(vertex);
        Collections.reverse(path);
        return path;
    }


    public static void main(String[] args) {
        DijkstraVertex v0 = new DijkstraVertex("Redvile");
        DijkstraVertex v1 = new DijkstraVertex("Blueville");
        DijkstraVertex v2 = new DijkstraVertex("Greenville");
        DijkstraVertex v3 = new DijkstraVertex("Orangeville");
        DijkstraVertex v4 = new DijkstraVertex("Purpleville");

        v0.adjacencies = new DijkstraEdge[]{new DijkstraEdge(v1, 5),
                new DijkstraEdge(v2, 10),
                new DijkstraEdge(v3, 8)};
        v1.adjacencies = new DijkstraEdge[]{new DijkstraEdge(v0, 5),
                new DijkstraEdge(v2, 3),
                new DijkstraEdge(v4, 7)};
        v2.adjacencies = new DijkstraEdge[]{new DijkstraEdge(v0, 10),
                new DijkstraEdge(v1, 3)};
        v3.adjacencies = new DijkstraEdge[]{new DijkstraEdge(v0, 8),
                new DijkstraEdge(v4, 2)};
        v4.adjacencies = new DijkstraEdge[]{new DijkstraEdge(v1, 7),
                new DijkstraEdge(v3, 2)};
        DijkstraVertex[] vertices = {v0, v1, v2, v3, v4};
        computePaths(v0, Arrays.asList(vertices));

        for (DijkstraVertex v : vertices) {
            System.out.println("Distance to " + v + ": " + v.minDistanceToSource);
            List<DijkstraVertex> path = getShortestPathTo(v);
            System.out.println("Path: " + path);
        }
    }

    static class DijkstraVertex implements Comparable<DijkstraVertex> {
        public final String name;
        public DijkstraEdge[] adjacencies;
        public double minDistanceToSource = Double.POSITIVE_INFINITY;
        public DijkstraVertex previous;

        public DijkstraVertex(String argName) {
            this.name = argName;
        }

        public String toString() {
            return name;
        }

        public int compareTo(DijkstraVertex other) {
            return Double.compare(minDistanceToSource, other.minDistanceToSource);
        }
    }

    static class DijkstraEdge {
        public final DijkstraVertex target;
        public final double weight;

        public DijkstraEdge(DijkstraVertex argTarget, double argWeight) {
            target = argTarget;
            weight = argWeight;
        }
    }


}